package club.vann.nowcoder;

import club.vann.nowcoder.common.ListNode;

/**
 * <p>难度：Medium</p>
 * <p>题目：链表中环的入口节点</p>
 * <p>描述：对于一个给定的链表，返回环的入口节点，如果没有环，返回null
 * 拓展：
 * 你能给出不利用额外空间的解法么？</p>
 * @author vann
 * @Title:
 * @Description:
 * @date 2021/6/16 10:13
 */
public class NC3 {
    public static void main(String[] args) {
        NC3 nc = new NC3();


    }

    /**
     * 解法一：
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        // 利用快慢指针判断链表是否有环？
        ListNode slow = head;
        ListNode fast = head.next.next;
        while(fast != null && fast.next != null) {
            // 有环
            if(fast == slow) {
                ListNode cur = head;
                while(cur != slow) {
                    cur = cur.next;
                    slow = slow.next;
                }
                return cur;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return null;
    }

    static class TestCase {
        public static ListNode ANS = null;
        public static ListNode HEAD = ListNode.deserialize("[1,2,3,4,5]");

        public static ListNode ANS1 = null;
        public static ListNode HEAD1 = ListNode.deserialize("[1,2,3,4,5]");
    }
}
